package April.解码方法0421;

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];

    }
}
/*
* 思路与算法

对于给定的字符串 ss，设它的长度为 nn，其中的字符从左到右依次为 s[1], s[2], \cdots, s[n]s[1],s[2],⋯,s[n]。我们可以使用动态规划的方法计算出字符串 ss 的解码方法数。

具体地，设 f_if
i
​
  表示字符串 ss 的前 ii 个字符 s[1..i]s[1..i] 的解码方法数。在进行状态转移时，我们可以考虑最后一次解码使用了 ss 中的哪些字符，那么会有下面的两种情况：

第一种情况是我们使用了一个字符，即 s[i]s[i] 进行解码，那么只要 s[i] \neq 0s[i]

​
 =0，它就可以被解码成 \text{A} \sim \text{I}A∼I 中的某个字母。由于剩余的前 i-1i−1 个字符的解码方法数为 f_{i-1}f
i−1
​
 ，因此我们可以写出状态转移方程：

f_i = f_{i-1}, \quad 其中 ~ s[i] \neq 0
f
i
​
 =f
i−1
​
 ,其中 s[i]

​
 =0

第二种情况是我们使用了两个字符，即 s[i-1]s[i−1] 和 s[i]s[i] 进行编码。与第一种情况类似，s[i-1]s[i−1] 不能等于 00，并且 s[i-1]s[i−1] 和 s[i]s[i] 组成的整数必须小于等于 2626，这样它们就可以被解码成 \text{J} \sim \text{Z}J∼Z 中的某个字母。由于剩余的前 i-2i−2 个字符的解码方法数为 f_{i-2}f
i−2
​
 ，因此我们可以写出状态转移方程：

f_i = f_{i-2}, \quad 其中 ~ s[i-1] \neq 0 ~并且~ 10\cdot s[i-1]+s[i] \leq 26
f
i
​
 =f
i−2
​
 ,其中 s[i−1]

​
 =0 并且 10⋅s[i−1]+s[i]≤26

需要注意的是，只有当 i>1i>1 时才能进行转移，否则 s[i-1]s[i−1] 不存在。

将上面的两种状态转移方程在对应的条件满足时进行累加，即可得到 f_if
i
​
  的值。在动态规划完成后，最终的答案即为 f_nf
n
​
 。

细节

动态规划的边界条件为：

f_0 = 1
f
0
​
 =1

即空字符串可以有 11 种解码方法，解码出一个空字符串。

同时，由于在大部分语言中，字符串的下标是从 00 而不是 11 开始的，因此在代码的编写过程中，我们需要将所有字符串的下标减去 11，与使用的语言保持一致。

*
*
* */